Show that \({2^n} \equiv {( - 1)^n}(\bmod 3)\), where \(n \in \mathbb{N}\).

Hence show that an integer is divisible by 3 if and only if the difference between the sum of its binary (base 2) digits in even-numbered positions and the sum of its binary digits in odd-numbered positions is divisible by 3.

Express the hexadecimal (base 16) number \({\text{ABB}}{{\text{A}}_{{\text{16}}}}\) in binary.

METHOD 1

\({2^n} = {(3 - 1)^n}\)    M1

\( = {3^n} + n{3^{n - 1}}( - 1) + \frac{{n(n - 1)}}{2}{3^{n - 2}}{( - 1)^2} + {\text{ }} \ldots {\text{ }} + {( - 1)^n}\)    A1

since all terms apart from the last one are divisible by 3     R1

\({2^n} \equiv {( - 1)^n}(\bmod 3)\)    AG

METHOD 2

attempt to reduce the powers of \(2(\bmod 3)\)     M1

\({2^0} = 1(\bmod 3);{\text{ }}{2^1} =  - 1(\bmod 3);{\text{ }}{2^2} = 1(\bmod 3);{\text{ }}{2^3} =  - 1(\bmod 3){\text{ }} \ldots \)    A1

since \(1(\bmod 3) \times 2 =  - 1(\bmod 3)\) and \( - 1(\bmod 3) \times 2 = 1(\bmod 3)\) the result can be generalized     R1

\(2n \equiv {( - 1)^n}(\bmod 3)\)    AG

[3 marks]

the binary number \(N = {({a_n}{a_{n - 1}} \ldots {a_2}{a_1}{a_0})_2}\) has numerical value

\({a_0} \times 1 + {a_1} \times 2 + {a_2} \times {2^2} +  \ldots  + {a_n} \times {2^n}\)    A1

\(N = \left( {{a_0} - {a_1} + {a_2} -  \ldots {{( - 1)}^n}{a_n}} \right)(\bmod 3)\)    M1A1

hence divisibility of \(N\) by 3 coincides with statement of question     AG

[3 marks]

\({\text{ABB}}{{\text{A}}_{16}} = 10 \times {16^3} + 11 \times {16^2} + 11 \times 16 + 10 \times 1\)    (A1)

\(N = {(1010)_2} \times {2^{12}} + {(1011)_2} \times {2^8} + {(1011)_2} \times {2^4} + {(1010)_2} \times {2^0}\)     (M1)(A1)

Note:     Award M1 for expressing A and B in binary.

\(N = {(1010101110111010)_2}\)    A1

[4 marks]

Many candidates were able to make a beginning to this question and attempted a solution to part (a). Some were let down by being unable to fully explain their reasoning.

In part (b) a number of fully correct answers were seen but some candidates appeared to be completely unaware of what constituted a sensible approach.

Again in part (c) a number of correct answers were seen but a significant number also appeared to have little idea on how to start.

Find \({H_2}\), \({H_3}\) and \({H_4}\).

Conjecture a formula for \({H_n}\) in terms of \(n\), for \(n \in {\mathbb{Z}^ + }\).

Prove by mathematical induction that your formula is valid for all \(n \in {\mathbb{Z}^ + }\).

\({H_2} = 2{H_1} + 1\)    (M1)

\( = 3;{\text{ }}{H_3} = 7;{\text{ }}{H_4} = 15\)    A1

[2 marks]

\({H_n} = {2^n} - 1\)    A1

[1 mark]

let \({\text{P}}(n)\) be the proposition that \({H_n} = {2^n} - 1\) for \(n \in {\mathbb{Z}^ + }\)

from (a) \({H_1} = 1 = {2^1} - 1\)     A1

so \({\text{P}}(1)\) is true

assume \({\text{P}}(k)\) is true for some \(k \Rightarrow {H_k} = {2^k} - 1\)     M1

then \({H_{k + 1}} = 2{H_k} + 1\)     (M1)

\( = 2 \times ({2^k} - 1) + 1\)    A1

\( = {2^{k + 1}} - 1\)

\({\text{P}}(1)\) is true and \({\text{P}}(k)\) is true \( \Rightarrow {\text{P}}(k + 1)\) is true, hence \({\text{P}}(n)\) is true for all \(n \in {\mathbb{Z}^ + }\) by the principle of mathematical induction     R1

Note:     Only award the R1 if all earlier marks have been awarded.

[5 marks]

This was a successful question for many candidates with many wholly correct answers seen. The vast majority of candidates were able to answer parts (a) and (b) and most knew how to start part (c). A few candidates were let down by not realising the need for a degree of formality in the presentation of the inductive proof.

This was a successful question for many candidates with many wholly correct answers seen. The vast majority of candidates were able to answer parts (a) and (b) and most knew how to start part (c). A few candidates were let down by not realising the need for a degree of formality in the presentation of the inductive proof.

This was a successful question for many candidates with many wholly correct answers seen. The vast majority of candidates were able to answer parts (a) and (b) and most knew how to start part (c). A few candidates were let down by not realising the need for a degree of formality in the presentation of the inductive proof.

Find the general solution to this equation.

Hence find the solution with minimum positive value of \(xy\).

Find the solution satisfying \(xy = 2014\).

one solution is \(x =  - 2,{\text{ }}y =  - 3{\text{ }}\left( {{\text{or }}(3,{\text{ }}4)} \right)\)     (A1)

the general solution is

\(x =  - 2 + 5N,{\text{ }}y =  - 3 + 7N{\text{ }}({\text{or }}x = 3 + 5M,{\text{ }}y = 4 + 7M)\)    M1A1

[3 marks]

a listing of small values of the product     (M1)

\( \Rightarrow x =  - 2,{\text{ }}y =  - 3\) (the least positive value of \(xy\) is 6)     A1

[2 marks]

use of “table” or otherwise to solve

\(35{N^2} - 29N + 6 = 2014{\text{ }}({\text{or }}35{M^2} + 41M + 12 = 2014)\)    (M1)

obtain \(N = 8{\text{ }}({\text{or }}M = 7)\)     (A1)

\(x = 38,{\text{ }}y = 53\)    A1

[3 marks]

This was also a very successful question with many wholly correct answers seen. A small number of candidates made arithmetic errors in the calculations. Some candidates used unnecessarily long and complex methods for parts (b) and (c) which would have potentially left them short of time elsewhere.

This was also a very successful question with many wholly correct answers seen. A small number of candidates made arithmetic errors in the calculations. Some candidates used unnecessarily long and complex methods for parts (b) and (c) which would have potentially left them short of time elsewhere.

This was also a very successful question with many wholly correct answers seen. A small number of candidates made arithmetic errors in the calculations. Some candidates used unnecessarily long and complex methods for parts (b) and (c) which would have potentially left them short of time elsewhere.

A number written in base 5 is 4303. Find this as a number written in base 10.

1000 is a number written in base 10. Find this as a number written in base 7.

4303₅ = 4 × 5³ + 3 × 5² + 0 × 5¹ + 3 × 5⁰        (M1)
= 500 + 75 + 3
= 578        A1

[2 marks]

METHOD 1

\(1000 = {a_0} + 7{a_1} + 49{a_2} + 343{a_3}\)      (M1)

(since \(343{a_3} < 1000\))\( \Rightarrow {a_3} = 2\)     (A1)

\(1000 = {a_0} + 7{a_1} + 49{a_2} + 686\)

\({a_0} + 7{a_1} + 49{a_2} = 314 \Rightarrow {a_2} = 6\)     (A1)

\({a_0} + 7{a_1} = 20 \Rightarrow {a_1} = 2,\,\,{a_0} = 6\)     (A1)

\( \Rightarrow {1000_{10}} = {2626_7}\)      A1

METHOD 2

1000 = 7 × 142 + 6      (M1)

142 = 7 × 20 + 2     (A1)

20 = 7 × 2 + 6     (A1)

2 = 7 × 0 + 2     (A1)

⇒ (1000)₁₀ = 2626₇      A1

[5 marks]

Without attempting to draw \(J\), verify that J satisfies the handshaking lemma;

Without attempting to draw \(J\), determine the number of faces in \(J\).

The vertices D and G are joined by a single edge to form the graph \(K\). Show that \(K\) is not planar.

Explain why a graph containing a cycle of length three cannot be bipartite. 

Hence by finding a cycle of length three, show that the complement of \(K\) is not bipartite.

the sum of degrees of the vertices is even (36) or the sum of degrees of the vertices is twice the number of edges A1

[2 marks]

the number of edges \((e)\) is 18     A1

using Euler’s relation \(v - e + f = 2\)     M1

\(f = 2 + 18 - 8 = 12\)     A1

[2 marks]

if \(K\) is planar then \(e \leqslant 3v - 6\)     M1

\(v = 8\) and \(e = 19\)     A1

the inequality is not satisfied so \(K\) is not planar     A1AG

[3 marks]

let PQRP be a cycle of length 3 in a graph     M1

Note:     Accept a diagram instead of this statement.

suppose the graph is bipartite

then P must belong to one of the two disjoint sets of vertices and Q, R must belong to the other disjoint set     R1

but Q, R cannot belong to the same set because they are linked     R1

therefore the graph cannot be bipartite     AG

[??? marks]

for example, a suitable cycle of order 3 is AFHA     (M1)A1

Note:     Award M1 for a valid attempt at drawing the complement or constructing its adjacency table.

[??? marks]

Use the Euclidean algorithm to find the greatest common divisor of 74 and 383.

Hence find integers s and t such that 74s + 383t = 1.

383 = 5 × 74 + 13        M1
74 = 5 × 13 + 9       A1
13 = 1 × 9 + 4       (A1)
9 = 2 × 4 + 1
4 = 4 × 1 + 0
⇒ gcd (74, 383) = 1       A1

[4 marks]

EITHER
1 = 9 − 2 × 4       (M1)
= 9 − 2(13 − 1 × 9) = 3 × 9 − 2 × 13        (A1)
= 3(74 − 5 × 13) − 2 × 13 = 3 × 74 − 17 × 13      (A1)
= 3 × 74 − 17 (383 − 5 × 74) = 88 × 74 − 17 × 383

OR
13 = 383 − 5 × 74      (M1)
9 = 74 − 5 × 13
  = 74 − 5(383 − 5 × 74)
  = 26 × 74 − 5 × 383      (A1)
4 = 13 − 9
  = (383 − 5 × 74) − (26 × 74 − 5 × 383)
  = 6 × 383 − 31 × 74      (A1)
1 = 9 − 2 × 4
  = (26 × 74 − 5 × 383) − 2(6 × 383 − 31 × 74)
  = 88 × 74 − 17 × 383

THEN
⇒ s = 88 and t =  − 17      A1A1

[5 marks]

Given that \(a \equiv b(\bmod p)\) , show that \({a^n} \equiv {b^n}(\bmod p)\) for all \(n \in {\mathbb{Z}^ + }\) .

Show that \({29^{13}} + {13^{29}}\) is exactly divisible by \(7\).

\(a \equiv b(\bmod p) \Rightarrow a = b + pN,N \in \mathbb{Z}\)      M1

\({a^n} = {(b + pN)^n} = {b^n} + n{b^{n - 1}}pN \ldots \)     M1A1

\( = {b^n} + pM\) where \(M \in \mathbb{Z}\)     A1

this shows that \({a^n} \equiv {b^n}(\bmod p)\)     AG

[4 marks]

\(29 \equiv 1(\bmod 7) \Rightarrow {29^{13}} \equiv {1^{13}} \equiv 1(\bmod 7)\)     M1A1

\(13 \equiv - 1(\bmod 7) \Rightarrow {13^{29}} \equiv {( - 1)^{29}} \equiv - 1(\bmod 7)\)     A1

therefore \({29^{13}} + {13^{29}} \equiv 1 + ( - 1) \equiv 0(\bmod 7)\)     M1A1

this shows that \({29^{13}} + {13^{29}}\) is exactly divisible by \(7\)     AG

[5 marks]

Find the general solution to the Diophantine equation \(3x + 5y = 7\).

Find the values of \(x\) and \(y\) satisfying the equation for which \(x\) has the smallest positive integer value greater than \(50\).

by any method including trial and error or the Euclidean algorithm, a specific solution is, for example, \(x = 4,{\text{ }}y =  - 1\)     (A1)(A1)

\(3(4) + 5( - 1) = 7\;\;\;\)(equation i)

\(3x + 5y = 7\;\;\;\)(equation ii)

equation ii – equation i: \(3(x - 4) + 5(y + 1) = 0\)

\(\frac{{4 - x}}{5} = \frac{{y + 1}}{3} = N\)     (M1)

\(x = 4 - 5N\)     A1

\(y = 3N - 1\)     A1

smallest positive integer \( > 50\) occurs when \(N =  - 10\)     (M1)

\(x = 54,{\text{ }}y =  - 31\)     A1

This question was well answered in general although a minority appeared not to realise that Diophantine means a solution in integers. It was expected that candidates would find a particular solution by inspection but some took a little longer by going via the Euclidean Algorithm.

This question was well answered in general although a minority appeared not to realise that Diophantine means a solution in integers. It was expected that candidates would find a particular solution by inspection but some took a little longer by going via the Euclidean Algorithm.

Consider the linear congruence \(ax \equiv b(\bmod p)\) where \(a,{\text{ }}b \in {\mathbb{Z}^ + },{\text{ }}p\) is a prime and \(\gcd (a,{\text{ }}p) = 1\). Using Fermat’s little theorem, show that \(x \equiv {a^{p - 2}}b(\bmod p)\).

Hence find the smallest value of \(x\) greater than 100 satisfying the linear congruence \(3x \equiv 13(\bmod 19)\).

multiplying both sides by \({a^{p - 2}}\),     M1

\({a^{p - 1}}x \equiv {a^{p - 2}}b(\bmod p)\)     A1

using \({a^{p - 1}} \equiv 1(\bmod p)\)     R1

therefore, \(x \equiv {a^{p - 2}}b(\bmod p)\)     AG

[3 marks]

using the above result,

\(x \equiv {3^{17}} \times 13(\bmod 19){\text{ }}\left( { \equiv 16\,7882\,2119(\bmod 19)} \right)\)     A1

\( \equiv 17(\bmod 19)\)     (M1)A1

\(x = 112\)     A1

[4 marks]

Use the Euclidean algorithm to find \(\gcd (162,{\text{ }}5982)\).

The relation \(R\) is defined on \({\mathbb{Z}^ + }\) by \(nRm\) if and only if \(\gcd (n,{\text{ }}m) = 2\).

(i)     By finding counterexamples show that \(R\) is neither reflexive nor transitive.

(ii)     Write down the set of solutions of \(nR6\).

\(5982 = 162 \times 36 + 150\)    M1A1

\(162 = 150 \times 1 + 12\)    A1

\(150 = 12 \times 12 + 6\)

\(12 = 6 \times 2 + 0 \Rightarrow \gcd \) is 6     A1

[4 marks]

(i)     for example, \(\gcd (4,{\text{ }}4) = 4\)     A1

\(4 \ne 2\)    R1

so \(R\) is not reflexive     AG

for example

\(\gcd (4,{\text{ }}2) = 2\) and \(\gcd (2,{\text{ }}8) = 2\)     M1A1

but \(\gcd (4,{\text{ }}8) = 4{\text{ }}( \ne 2)\)     R1

so \(R\) is not transitive     AG

(ii)     EITHER

even numbers     A1

not divisible by 6     A1

OR

\(\{ 2 + 6n:n \in \mathbb{N}\} {\text{ }} \cup \{ 4 + 6n:n \in \mathbb{N}\} \)   A1A1

OR

\(2,{\text{ }}4,{\text{ }}8,{\text{ }}10,{\text{ }} \ldots \)    A2

[7 marks]

This was a successful question for many students with many wholly correct answers seen. Part (a) was successfully answered by most candidates and those candidates usually had a reasonable understanding of how to complete part (b). A number were not fully successful in knowing how to explain their results.

This was a successful question for many students with many wholly correct answers seen. Part (a) was successfully answered by most candidates and those candidates usually had a reasonable understanding of how to complete part (b). A number were not fully successful in knowing how to explain their results.

Express the number \(47502\) as a product of its prime factors.

The positive integers \(M\) , \(N\) are such that \(\gcd (M,N) = 63\) and \(lcm(M,N) = 47502\) . Given that \(M\) is even and \(M < N\) , find the two possible pairs of values for \(M\) , \(N\) .

      (M1)

therefore \(47502 = 2 \times {3^2} \times 7 \times 13 \times 29\)     A1

[2 marks]

noting that \(MN = \gcd \times {\rm{lcm}} = 2 \times {3^4} \times {7^2} \times 13 \times 29\)     (M1)

the possibilities are

\((M,N) = (126,23751)\)     A1A1

\((M,N) = (1638,1827)\)     A1A1

[5 marks]

As expected, the factorization in (a) was successfully completed by most candidates.

Part (b) caused problems for some candidates. The most common mistake was that only one pair of values for \(M\), \(N\) was given.

Solve the recurrence relation \({u_n} = 4{u_{n - 1}} - 4{u_{n - 2}}\) given that \({u_0} = {u_1} = 1\).

Consider \({v_n}\) which satisfies the recurrence relation \(2{v_n} = 7{v_{n - 1}} - 3{v_{n - 2}}\) subject to the initial conditions \({v_0} = {v_1} = 1\).

Prove by using strong induction that \({v_n} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^n} + \frac{1}{5}{\left( 3 \right)^n}\) for \(n \in \mathbb{N}\).

auxiliary equation is \({m^2} - 4m + 4 = 0\)      M1A1

hence \(m\) has a repeated root of 2     (A1)

solution is of the form \({u_n} = a{\left( 2 \right)^n} + bn{\left( 2 \right)^n}\)     M1

using the initial conditions      M1

\( \Rightarrow a = 1\) and \(b =  - \frac{1}{2}\)

\( \Rightarrow {u_n} = {2^n} - \frac{n}{2}{\left( 2 \right)^n}\)      A1

[6 marks]

\({v_n} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^n} + \frac{1}{5}{\left( 3 \right)^n}\)

let \(n = 0\)  \({v_0} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^0} + \frac{1}{5}{\left( 3 \right)^0} = \frac{4}{5} + \frac{1}{5} = 1\)

let \(n = 1\)  \({v_1} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^1} + \frac{1}{5}{\left( 3 \right)^1} = \frac{2}{5} + \frac{3}{5} = 1\)

hence true for \(n = 0\) and \(n = 1\)       M1A1

assume that \({v_j} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^j} + \frac{1}{5}{\left( 3 \right)^j}\) is true for all \(j > k + 1\)       M1

hence \({v_k} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^k} + \frac{1}{5}{\left( 3 \right)^k}\) and \({v_{k - 1}} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^{k - 1}} + \frac{1}{5}{\left( 3 \right)^{k - 1}}\)

\({v_{k + 1}} = \frac{{7{v_k} - 3{v_{k - 1}}}}{2}\)

\({v_{k + 1}} = \frac{{7\left[ {\frac{4}{5}{{\left( {\frac{1}{2}} \right)}^k} + \frac{1}{5}{{\left( 3 \right)}^k}} \right] - 3\left[ {\frac{4}{5}{{\left( {\frac{1}{2}} \right)}^{k - 1}} + \frac{1}{5}{{\left( 3 \right)}^{k - 1}}} \right]}}{2}\)      M1A1

\({v_{k + 1}} = \frac{{7\left[ {\frac{8}{5}{{\left( {\frac{1}{2}} \right)}^{k + 1}} + \frac{1}{{15}}{{\left( 3 \right)}^{k + 1}}} \right] - 3\left[ {\frac{{16}}{5}{{\left( {\frac{1}{2}} \right)}^{k + 1}} + \frac{1}{{45}}{{\left( 3 \right)}^{k + 1}}} \right]}}{2}\)       (A1)

\({v_{k + 1}} = \frac{{\frac{{56}}{5}{{\left( {\frac{1}{2}} \right)}^{k + 1}} + \frac{7}{{15}}{{\left( 3 \right)}^{k + 1}} - \frac{{48}}{5}{{\left( {\frac{1}{2}} \right)}^{k + 1}} - \frac{1}{{15}}{{\left( 3 \right)}^{k + 1}}}}{2}\)       (A1)

\({v_{k + 1}} = \frac{{\frac{8}{5}{{\left( {\frac{1}{2}} \right)}^{k + 1}} + \frac{6}{{15}}{{\left( 3 \right)}^{k + 1}}}}{2}\)       (A1)

Note: Only one of the above (A1) can be implied.

\({v_{k + 1}} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^{k + 1}} + \frac{1}{{15}}{\left( 3 \right)^{k + 1}}\)

since the basis step and the inductive step have been verified, the Principle of Mathematical Induction tells us that \({v_n} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^n} + \frac{1}{5}{\left( 3 \right)^n}\) is
the general solution        R1

[9 marks]

Note: Only award final R1 if at least 5 previous marks have been awarded.

Prove that \(3k + 2\) and \(5k + 3\) , \(k \in \mathbb{Z}\) are relatively prime.

EITHER

\(3k + 2\) and \(5k + 3\) , \(k \in \mathbb{Z}\) are relatively prime

if, for all \(k\) , there exist \(m,n \in \mathbb{Z}\) such that

\(m(3k + 2) + n(5k + 3) = 1\)     R1M1A1 

\( \Rightarrow 3m + 5n = 0\)     A1

\(2m + 3n = 1\)     A1

\(m = 5\) , \(n = - 3\)     A1

hence they are relatively prime     AG

OR

\(5k + 3 = 1 \times (3k + 2) + 2k + 1\)     M1A1

\(3k + 2 = 1 \times (2k + 1) + k + 1\)     A1

\(2k + 1 = 1 \times (k + 1) + k\)     A1

\(k + 1 = 1 \times (k) + 1\)     A1

GDC = 1     A1

so \(5k + 3\) and \(3k + 2\) are relatively prime     AG

[6 marks]

This was often done using Euclid's algorithm rather than writing \(m(3k + 2) + n(5k + 3) = 1\) for the relatively prime numbers.

Prove that the number \(14 641\) is the fourth power of an integer in any base greater than \(6\).

For \(a,b \in \mathbb{Z}\) the relation \(aRb\) is defined if and only if \(\frac{a}{b} = {2^k}\) , \(k \in \mathbb{Z}\) .

  (i)     Prove that \(R\) is an equivalence relation.

  (ii)     List the equivalence classes of \(R\) on the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

\(14641\) (base \(a > 6\) ) \( = {a^4} + 4{a^3} + 6{a^2} + 4a + 1\) ,     M1A1

\( = {(a + 1)^4}\)     A1

this is the fourth power of an integer     AG

[3 marks]

(i)     \(aRa\) since \(\frac{a}{a} = 1 = {2^0}\) , hence \(R\) is reflexive     A1

\(aRb \Rightarrow \frac{a}{b} = {2^k} \Rightarrow \frac{b}{a} = {2^{ - k}} \Rightarrow bRa\)

so R is symmetric     A1

\(aRb\) and \(bRc \Rightarrow \frac{a}{b} = {2^m}\), \(m \in \mathbb{Z}\) and \(bRc \Rightarrow \frac{b}{c} = {2^n}\) , \(n \in \mathbb{Z}\)     M1

\( \Rightarrow \frac{a}{b} \times \frac{b}{c} = \frac{a}{c} = {2^{m + n}}\) , \(m + n \in \mathbb{Z}\)    A1

\( \Rightarrow aRc\) so transitive     R1

hence \(R\) is an equivalence relation     AG

(ii)     equivalence classes are {1, 2, 4, 8} , {3, 6} , {5, 10} , {7} , {9}     A3

Note: Award A2 if one class missing, A1 if two classes missing, A0 if three or more classes missing.

[8 marks]

This was not difficult but a surprising number of candidates were unable to do it. Care with notation and logic were lacking.

The question was at first straightforward but some candidates mixed up the properties of an equivalence relation with those of a group. The idea of an equivalence class is still not clearly understood by many candidates so that some were missing.

Using mathematical induction or otherwise, prove that the number \({(1020)_n}\) , that is the number \(1020\) written with base \(n\) , is divisible by \(3\) for all values of \(n\) greater than \(2\).

Explain briefly why the case \(n = 2\) has to be excluded.

\({(1020)_n} = {n^3} + 2n\)     (R1)

so we are required to prove that \({n^3} + 2n\) is divisible by \(3\) for \(n \ge 3\)     (R1)

EITHER

when \(n = 3\) , \({n^3} + 2n = 33\) which is divisible by \(3\) so the result is true for \(n = 3\)     A1

assume the result is true for \(n = k\) , i.e. \({k^3} + 2k\) is divisible by \(3\)     M1

for \(n = k + 1\) ,

\({(k + 1)^3} + 2(k + 1) = {k^3} + 3{k^2} + 3k + 1 + 2k + 2\)     M1

\( = ({k^3} + 2k) + 3({k^2} + k + 1)\)     A1

the second term is clearly divisible by \(3\) and the first term is divisible by \(3\) by hypothesis     A1

therefore true for \(n = k \Rightarrow \)  true for \(n = k + 1\) and since shown true for \(n = 3\) ,

the result is proved by induction     R1

Note: Award the final R1 only if the two M1 marks have been awarded.

OR

there are three cases to consider, let \(N\) be a positive integer

case 1: \(n = 3N\) , in this case

\(n({n^2} + 2) = 3N(9{N^2} + 2)\) which is divisible by \(3\)     M1A1

case 2: \(n = 3N + 1\) , in this case,

\(n({n^2} + 2) = (3N + 1)(9{N^2} + 6N + 3)\) which is divisible by \(3\)     M1A1

case 3: \(n = 3N + 2\) , in this case,

\(n({n^2} + 2) = (3N + 2)(9{N^2} + 12N + 6)\) which is divisible by \(3\)     M1A1

this proves the required result for all \(n > 2\)

[8 marks]

numbers to base \(2\) do not use the digit \(2\) or equivalent     R1

[1 mark]

A significant number of candidates struggled with this question, but a number of wholly correct answers were seen. The majority of candidates tried to use a method of proof by induction although a number got lost in trying to establish the result for \(k + 1\) . Again the presentation and explanation of some of the solutions was poor. Some excellent solutions were seen using other methods including one which noted simply that all positive integers \(n\) are either 0 or \( \pm 1\) modulo \(3\) so that \(n({n^2} + |2) \equiv 0\) modulo \(3\) for all \(n\).

A significant number of candidates struggled with this question, but a number of wholly correct answers were seen. The majority of candidates tried to use a method of proof by induction although a number got lost in trying to establish the result for \(k + 1\) . Again the presentation and explanation of some of the solutions was poor. Some excellent solutions were seen using other methods including one which noted simply that all positive integers \(n\) are either 0 or \( \pm 1\) modulo \(3\) so that \(n({n^2} + |2) \equiv 0\) modulo \(3\) for all \(n\).

Prove that if \({\rm{gcd}}(a,b) = 1\) and \({\rm{gcd}}(a,c) = 1\) , then \({\rm{gcd}}(a,bc) = 1\) .

(i)     A simple graph has e edges and v vertices, where \(v > 2\) . Prove that if all the vertices have degree at least k , then \(2e \ge kv\) .

(ii)     Hence prove that every planar graph has at least one vertex of degree less than 6.

EITHER

since \({\rm{gcd}}(a,b) = 1\) and \({\rm{gcd}}(a,c) = 1\) then

\(ax + by = 1\) and \(ap + cq = 1\) for \(x\), \(y\) , \(p\), \(q \in \mathbb{Z}\)     M1A1

hence

\((ax + by)(ap + cq) = 1\)     A1

\(a(xap + xcq + byp) + bc(yq) = 1\)     M1

since \((xap + xcq + byp)\) and \((yq)\) are integers     R1

then \({\rm{gcd}}(a,bc) = 1\)     AG

OR

if \({\rm{gcd}}(a,bc) \ne 1\) , some prime p divides a and bc     M1A1

\(p\) divides \(b\) or \(c\)     M1

either \({\rm{gcd}}(a,b)\) or \({\rm{gcd}}(a,c) \ne 1\)     A1

contradiction \( \Rightarrow {\rm{gcd}}(a,bc) = 1\)     R1

[5 marks]

(i)     each edge contributes 2 to the degree sum     R1

so \(2e = \) degree sum     R1

so \(2e \ge kv\)     AG

(ii)     \(k = 6\) so \(2e \ge 6v\)     M1

for a planar graph with \(v\) vertices and e edges, \(e \le 3v - 6\)     M1

so \(2e \le 6v - 12\)     A1

this is a contradiction so at least one vertex must have degree \( < 6\)     R1

Note: Alternative proofs are possible.

[6 marks]

A "verbal" argument rather than a symbolic approach was often taken, leading to some doubt about the validity of the "proofs". This discursive approach in trying to prove propositions often leads down blind alleys to confusion.

This was reasonably well done although clear proofs were not abundant and the same comments mentioned in (a) apply. In (ii) the word "Hence" was sometimes ignored. Candidates should realize that such "signpost" words are there to help them.

Determine whether or not \(G\) is bipartite.

(i)     Write down the adjacency matrix for \(G\).

(ii)     Find the number of distinct walks of length \(4\) beginning and ending at A.

\(G\) is bipartite     A1

because it contains a triangle.     R1

Note: Award R1 for a valid attempt at showing that the vertices cannot be divided into two disjoint sets.

[2 marks]

(i)

\({\boldsymbol{M}} = \left( {\begin{array}{*{20}{c}}
  0&1&0&0&0&1 \\
  1&0&1&1&1&0 \\
  0&1&0&1&0&0 \\
  0&1&1&0&1&1 \\
  0&1&0&1&0&1 \\
  1&0&0&1&1&0
\end{array}} \right)\)     A1

(ii)     We require the (A, A) element of \({\boldsymbol{M}^4}\) which is \(13\).     M1A2

[4 marks]

Use the Euclidean Algorithm to show that \(275\) and \(378\) are relatively prime.

Find the general solution to the diophantine equation \(275x + 378y = 1\) .

\(378 = 1 \times 275 + 103\)     A1

\(275 = 2 \times 103 + 69\)     A1

\(103 = 1 \times 69 + 34\)     A1

\(69 = 2 \times 34 + 1\)     A1

showing that gcd \( = 1\) , i.e. relatively prime.     R1

[5 marks]

Working backwards,

\(1 = 69 - 2 \times (103 - 69)\)     (M1)

\( = 3 \times 69 - 2 \times 103\)     (A1)

\( = 3 \times (275 - 2 \times 103) - 2 \times 103\)

\( = 3 \times 275 - 8 \times 103\)     (A1)

\( = 3 \times 275 - 8 \times (378 - 275)\)

\( = 11 \times 275 - 8 \times 378\)     (A1)

A solution is \(x = 11\) , \(y = - 8\)     (A1)

The general solution is \(x = 11 + 378n\) , \(y =  - 8 - 275n\) where \(n \in \mathbb{Z}\)      M1A1     N6

[7 marks]

In base \(5\) an integer is written \(1031\). Express this integer in base \(10\).

Given that \(N = 365,{\text{ }}r = 10\) and \(s = 7\) find the values of \({a_0},{\text{ }}{a_1},{\text{ }}{a_2},{\text{ }} \ldots \).

(i)     Given that \(N = 899,{\text{ }}r = 10\) and \(s = 12\) find the values of \({a_0},{\text{ }}{a_1},{\text{ }}{a_2},{\text{ }} \ldots \)

(ii)     Hence write down the integer in base \(12\), which is equivalent to \(899\) in base \(10\).

Show that \(121\) is always a square number in any base greater than \(2\).

\(1031 = 1 \times {5^3} + 0 \times {5^2} + 3 \times 5 + 1\)     M1

\( = 125 + 0 + 15 + 1\)

\( = 141\)     A1

\(365 = 1 \times {7^3} + 0 \times {7^2} + 3 \times 7 + 1\)     M1

\( \Rightarrow {a_0} = 1,{\text{ }}{a_1} = 3,{\text{ }}{a_2} = 0,{\text{ }}{a_3} = 1\)     A1

(i)     \(899 = 6 \times {12^2} + 2 \times 12 + 11\)     M1

\( \Rightarrow {a_0} = 11,{\text{ }}{a_1} = 2,{\text{ }}{a_2} = 6\)     A1

(ii)     \({(899)_{10}} = {(62B)_{12}}\)

(where \(B\) represents the digit in base \(12\) given by \({a_0} = 11\))     A1

Note: Accept any letter in place of \(B\) provided it is defined

\(121\) in base \(r\) is \(1 + 2r + {r^2}\)     M1A1

\( = {(r + 1)^2}\)     A1

which is a square for all \(r\)     AG

This question was very well answered in general, although some candidates failed to see that \(121 = {11^2}\) in all number bases greater than \(2\).

This question was very well answered in general, although some candidates failed to see that \(121 = {11^2}\) in all number bases greater than 2.

This question was very well answered in general, although some candidates failed to see that \(121 = {11^2}\) in all number bases greater than 2.

This question was very well answered in general, although some candidates failed to see that \(121 = {11^2}\) in all number bases greater than 2.

(i)     Use the Euclidean algorithm to find gcd(\(6750\), \(144\)) .

(ii)     Express your answer in the form \(6750r + 144s\) where r , \(s \in \mathbb{Z}\) .

Consider the base \(15\) number CBA, where A, B, C represent respectively the digits ten, eleven, twelve.

  (i)     Write this number in base \(10\).

  (ii)     Hence express this number as a product of prime factors, writing the factors in base 4.

(i)    \(6750 = 46 \times 144 + 126\)     M1A1

\(144 = 1 \times 126 + 18\)     A1

\(126 = 7 \times 18\)

\(\gcd(6750,144) = 18\)     A1 N0

(ii)     \(18 = 144 - 1 \times 126\)     (M1)

\( = 144 - (6750 - 46 \times 144)\)

\( = 47 \times 144 + ( - 1) \times 6750\)     A1

[6 marks]

(i)     \(n = 10 + 11 \times 15 + 12 \times {15^2}\)     (M1)(A1)

\( = 2875\)     A1

(ii)     \(2875 = {5^3} \times 23\)    A1

\( = 11 \times 11 \times 11 \times 113\) in base \(4\)     A1A1

Note: A1 for \(11 \times 11 \times 11\) ,  A1 for \(113\) .

[6 marks]

Most candidates were able to use the Euclidean algorithm to find a gcd and to express the answer in a different form. All but the weakest candidates were able to make a meaningful start to this question.

In part (b) many correct answers were seen and a majority of students were able to use the work they had studied on number bases correctly. All but the weakest candidates were able to make a meaningful start to this question.

(i)     Sum the series \(\sum\limits_{r = 0}^\infty  {{x^r}} \) .

(ii)     Hence, using sigma notation, deduce a series for

  (a)     \(\frac{1}{{1 + {x^2}}}\) ;

  (b)     \(\arctan x\) ;

  (c)     \(\frac{\pi }{6}\) .

Show that \(\sum\limits_{n = 1}^{100} {n! \equiv 3(\bmod 15)} \) .

(i)     \(\sum\limits_{r = 0}^\infty  {{x^r}}  = 1 + x + {x^2} + {x^3} + {x^4} +  \ldots  = \frac{1}{{1 - x}}\)     A1

(ii)     (a)     replacing x by \( - {x^2}\) gives     (M1)

\(\frac{1}{{1 - ( - {x^2})}} = 1 + ( - {x^2}) + {( - {x^2})^2} + {( - {x^2})^3} + {( - {x^2})^4} +  \ldots \)     A1

\(\frac{1}{{1 + {x^2}}} = 1 - {x^2} + {x^4} - {x^6} + {x^8} -  \ldots \)     (A1)

\( = \sum\limits_{r = 0}^\infty  {{{( - 1)}^r}{x^{2r}}} \)     A1     N2

(b)     \(\arctan x = \int {\frac{{{\rm{d}}x}}{{1 + {x^2}}}}  = x - \frac{{{x^3}}}{3} + \frac{{{x^5}}}{5} - \frac{{{x^7}}}{7} +  \ldots  + c\)     M1A1

\(x = 0 \Rightarrow c = 0\)     A1

\(\arctan x = \sum\limits_{r = 0}^\infty  {{{( - 1)}^r}\frac{{{x^{2r + 1}}}}{{2r + 1}}} \)     A1

(c)     by taking \(x = \frac{1}{{\sqrt 3 }}\)     M1

\(\arctan \frac{1}{{\sqrt 3 }} = \frac{\pi }{6} = \sum\limits_{r = 0}^\infty  {\frac{{{{( - 1)}^r}{{\left( {\frac{1}{{\sqrt 3 }}} \right)}^{2r + 1}}}}{{2r + 1}}} \)     A1

[11 marks]

\(\sum\limits_{n = 1}^{100} {n! = 1! + 2! + 3! + 4! + 5! +  \ldots } \)     M1     

\( = 1 + 2 + 6 + 24 + 120 +  \ldots \)

\( \equiv 1 + 2 + 6 + 24 + 0 + 0 + 0 +  \ldots (\bmod 15)\)     M1A1   

\( \equiv 33(\bmod 15)\)     A1

\( \equiv 3(\bmod 15)\)     AG

[4 marks]

In part (b) many did not recognize the sum of a simple geometric series to infinity and got involved in some heavy Maclaurin work thus wasting time. The clear instruction "Hence" was ignored by many candidates so that the question became more difficult and time consuming than it should have been.

Part (c) proved not to be as difficult as expected.

Determine the value of \(b\) .

Find the representation of \(N\)

  (i) in base \(10\);

  (ii) in base \(12\).

the equation satisfied by \(b\) is

\(4{b^3} + 6b + 4 = 2{(b + 1)^3} + 6{(b + 1)^2} + (b + 1) + 2\)     M1A1

\(2{b^3} - 12{b^2} - 13b - 7 = 0\)     (A1)

\(b = 7\)     A1

[4 marks]

(i)     \(N = 4 \times {7^3} + 6 \times 7 + 4 = 1418\)

or \(N = 2 \times {8^3} + 6 \times {8^2} + 1 \times 8 + 2 = 1418\)     (M1)A1

(ii)     \(12\left| \!{\underline {\,
  {1418} \,}} \right. \)     (M1)

\(12\left| \!{\underline {\,
  {118} \,}} \right. \) remainder \(2\)     (A1)

\(12\left| \!{\underline {\,
  9 \,}} \right. \) remainder A (where A \( = 10\) )     (A1)

\(1418 = {(9{\rm{A}}2)_{12}}\)     A1

Note: Accept alternative correct methods.

[6 marks]

Find the positive square root of the base 7 number \({(551662)_7}\), giving your answer as a base 7 number.

converting to base 10

\({(551662)_7} = 2 + 6 \times 7 + 6 \times {7^2} + 1 \times {7^3} + 5 \times {7^4} + 5 \times {7^5}\)     (M1)

\( = 96721\)     (A1)

\(\sqrt {96721}  = 311\)     A1

converting back to base 7

\(7)\underline {311} \)     (M1)

\()\underline {44} (3\)

\()\underline 6 (2\)     (A1)

it follows that \(\sqrt {{{(551662)}_7}}  = {(623)_7}\)     A1

Note: Accept \(623\).

[6 marks]

(a)     Show that the solution to the linear congruence \(ax \equiv b(\bmod p)\), where \(a,{\text{ }}x,{\text{ }}b,{\text{ }}p \in {\mathbb{Z}^ + },{\text{ }}p\) is prime and \(a\), \(p\) are relatively prime, is given by \(x \equiv {a^{p - 2}}b(\bmod p)\).

(b)     Consider the congruences

     \(7x \equiv 13(\bmod 19)\)

     \(2x \equiv 1(\bmod 7)\).

(i)     Use the result in (a) to solve the first congruence, giving your answer in the form \(x \equiv k(\bmod 19)\) where \(1 \leqslant k \leqslant 18\).

(ii)     Find the set of integers which satisfy both congruences simultaneously.

(a)     using Fermat’s little theorem,     (M1)

\({a^{p - 1}} \equiv 1(\bmod p)\)     A1

multiplying both sides of the congruence by \({a^{p - 2}}\),     (M1)

\({a^{p - 1}}x \equiv {a^{p - 2}}b(\bmod p)\)     A1

\(x \equiv {a^{p - 2}}b(\bmod p)\)     AG

[4 marks]

(b)     (i)     the solution is

\(x \equiv {7^{17}} \times 13(\bmod 19)\)     A1

consider

\({7^3} = 343 \equiv 1(\bmod 19)\)     (A1)

Note: Other powers are possible.

therefore

\(x \equiv {\left( {{7^3}} \right)^5} \times {7^2} \times 13(\bmod 19)\)     (A1)

\( \equiv {7^2} \times 13(\bmod 19)\)     (A1)

\( \equiv 10(\bmod 19)\)     A1

(ii)     using any method, including trial and error, the solution to the second congruence is given by \(x \equiv 32(\bmod 7)\) (or equivalent)     (A1)

a simultaneous solution is \(x = 67\) (or equivalent, eg \(-66\))     A1

the full solution is \(x = 67 + 133N\) (where \(N \in \mathbb{Z}\)) (or equivalent)     A1

Note: Do not FT an incorrect answer from (i).

[8 marks]

Given that \({n^2} + 2n + 3 \equiv N(\bmod 8)\) , where \(n \in {\mathbb{Z}^ + }\) and \(0 \le N \le 7\) , prove that \(N\) can take one of only three possible values.

consider the following

     M1A1A1

we see that the only possible values so far are \(2\), \(3\) and \(6\)     R1

also, the table suggests that these values repeat themselves but we have to prove this

let \(f(n) = {n^2} + 2n + 3\) , consider

\(f(n + 4) - f(n) = {(n + 4)^2} + 2(n + 4) + 3 - {n^2} - 2n - 3\)     M1

\( = 8n + 24\)     A1

since \(8n + 24\) is divisible by \(8\),     M1

\(f(n + 4) \equiv (n)(\bmod 8)\)     A1

this confirms that the values do repeat every \(4\) values of \(n\) so that \(2\), \(3\) and \(6\) are the only values taken for all values of \(n\)     R1

[9 marks]

Solutions to this question were extremely disappointing in general. Many candidates spotted that there was a periodicity in the values of the polynomial as far as \(n = 4\) and even \(n = 8\) but then the majority simply assumed that this would continue without any need for proof. This is equivalent to noting that \({2^{2n + 1}} - 1\) is prime for \(n = 1\), \(2\) and \(3\) and simply assuming that this will be true for larger values of \(n\).

A sequence \(\left\{ {{u_n}} \right\}\) satisfies the recurrence relation \({u_{n + 2}} = 2{u_{n + 1}} - 5{u_n}\) , \(n \in \mathbb{N}\) . Obtain an expression for \({u_n}\) in terms of n given that \({u_0} = 0\) and \({u_1} = 1\) .

the auxiliary equation is \({m^2} - 2m + 5 = 0\)    M1

the roots are \(1 \pm 2{\rm{i}}\)    A1

the general solution is \({u_n} = A{\left(1 + 2{\rm{i}}\right)^n} + B{\left(1 - 2{\rm{i}}\right)^n}\)     A1

substituting \({u_0} = 0\) and \({u_1} = 1\)     M1

\(A + B = 0\)

\(A(1 + 2{\rm{i}}) + B(1 - 2{\rm{i}}) = 1\)     A1

Note: Only award above A1 if both equations are correct.

solving

\(A\left(1 + 2{\rm{i}} - 1 + 2{\rm{i}}\right) = 1\)     (M1)

\(A = \frac{1}{{4{\rm{i}}}}\) or \( - \frac{{\rm{i}}}{4}\)     A1

\(B =  - \frac{1}{{4{\rm{i}}}}\) or \(\frac{{\rm{i}}}{4}\)     A1

therefore

\({u_n} = \frac{1}{{4{\rm{i}}}}{\left(1 + 2{\rm{i}}\right)^n} - \frac{1}{{4{\rm{i}}}}{\left(1 - 2{\rm{i}}\right)^n}\) or \(\frac{{\rm{i}}}{4}{\left(1 - 2{\rm{i}}\right)^n} - \frac{{\rm{i}}}{4}{\left(1 + 2{\rm{i}}\right)^n}\)     A1

[9 marks]

(ii)     Find the number of walks of length \(4\) beginning and ending at B.

(i)     Draw \(G'\), the complement of \(G\) .

(ii)     Write down the degrees of all the vertices of \(G\) and all the vertices of \(G'\).

(iii)     Hence, or otherwise, determine whether or not \(G\) and \(G'\) are isomorphic.

(i)     the adjacency matrix is

\(\left( {\begin{array}{*{20}{c}}
0&1&0&0&0\\
1&0&1&0&1\\
0&1&0&1&0\\
0&0&1&0&1\\
0&1&0&1&0
\end{array}} \right)\)     A2

Note: Award A2 for correct matrix, A1 for one or two errors and A0 for more than two errors.

(ii)     the required number of walks is the (B, B) element in the fourth power of the adjacency matrix     (M1) 

using a GDC gives the answer as 13     A2

[5 marks]

(i)

     A2

(ii)

     A1A1

(iii)     In \(G\), the vertex of degree 1 is adjacent to the vertex of degree 3, whereas in \(G'\) the vertex of degree \(1\) is adjacent to a vertex of degree \(2\). They are not therefore isomorphic.     A1R1

Note: Accept alternative correct solutions.

[6 marks]

Many candidates wrote down the adjacency matrix correctly and then proceeded to raise it to the fourth power, although at least one candidate actually enumerated, correctly, the \(13\) walks.

Part (b) was reasonably well done with many candidates realising that, although the degrees of the vertices were the same, their relative positions meant that the two graphs were not isomorphic.

Draw the simple graph \(G\).

Explain why \(G\) does not contain an Eulerian circuit.

Show that \(G\) has a Hamiltonian cycle.

State whether or not \(G\) is planar, giving a reason for your answer.

State whether or not the simple graph \(G\) is bipartite, giving a reason for your answer.

Draw the complement \(G'\) of \(G\).

     A1

because it has vertices which are not of even degree.     A1

for example \({\text{D}} \to {\text{C}} \to {\text{B}} \to {\text{E}} \to {\text{A}} \to {\text{F}} \to {\text{D}}\)     A2

\(G\) is planar.     A1

either note from original graph in part (a) that there are no edges crossing or a redrawing with statement that there are no edges crossing.     R1

Note: Do not accept an argument based on \(e \leqslant 3v - 6\)

the graph is not bipartite.     A1

EITHER

the graph contains a triangle     R1

OR

to be bipartite according to line 1 of the table A, C and D need to be one set as A connects to B, E and F. Since C and D are connected, this is contradicted.     R1

     A2

Note: Award A1 if extra line seen or missed out.

This question was very well answered in general.

This question was very well answered in general.

This question was very well answered in general.

This question was very well answered in general. In (d), some candidates stated that G is planar because \(e \leqslant 3v - 6\). It is however important to realise that this condition is necessary for a graph to be planar but not sufficient. Some candidates stated that G is planar ‘because I have drawn it as a planar graph’ or even ‘see graph in (a)’. Candidates were expected to state that G is planar because it can be drawn with no edges crossing.

This question was very well answered in general.

This question was very well answered in general.